struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};
//删除搜索二叉树的节点
//搜寻节点后有五种情况
/*
1.遇到叶子节点，没找到，不删除
找到了
2.叶子节点直接删除
3.有左子树，无右子树，删除节点并用右子树根节点代替
4.有右子树，无左子树，同上
5.左右子树都有，将左子树的根节点链接为右子树的最左边的节点的左孩子
*/



//递归法
//递归函数要返回函数，因此也要用一个指针来接收返回值
TreeNode* deleteNode(TreeNode* root, int key) {
    if(!root) return root;
    if(root->val==key){
        if(!root->left) return root->right;
        else if(!root->right) return root->left;
        else{       //左右子树都在，右子树代替该节点并将左节点放入右节点的最左边
        TreeNode* rtree_left=root->right;
        while(rtree_left->left) rtree_left=rtree_left->left;    //找到右子树的最左节点
        rtree_left->left=root->left;
        //删除节点要释放内存
        TreeNode* temp=root;
        root=root->right;
        delete temp;
        return root;
        }
    }
    //接收返回值
    if(root->val>key) root->left=deleteNode(root->left,key);        
    if(root->val<key) root->right=deleteNode(root->right,key);
    //读几次就会发现，虽然上面部分都是用root，但至始至终都没有实际修改root，所以返回root就可以
    return root; 
}



//迭代法
TreeNode* deleteNodeOP(TreeNode* target){
    if(!target) return nullptr;
    if(!target->left) return target->right;
    else if(!target->right) return target->left;
    TreeNode* cur=target->right;
    while(cur->left) cur=cur->left;
    TreeNode* temp=target;
    TreeNode* res=target->right;
    cur->left=target->left;
    delete temp;
    return res;
    //必须要记录res，因为target删除后无法找到target->right
}
//删除节点的操作

TreeNode* deleteNode(TreeNode* root, int key) {
    if(!root) return root;
    TreeNode* pre=nullptr;  //pre记录上一个节点
    TreeNode* cur=root;
    while(cur){
        if(cur->val==key) break;
        pre=cur;
        if(cur->val>key) cur=cur->left;
        else if(cur->val<key) cur=cur->right;
    }
    if(!pre) return deleteNodeOP(cur);      //pre为空，则树只有头结点
    if(pre->left&&pre->left->val==key) pre->left=deleteNodeOP(cur);
    else if(pre->right&&pre->right->val==key) pre->right=deleteNodeOP(cur);
    return root;

}